A queue refers to a data type used in computing. Within the queue, multiple items can be stored in a particular order. Items can be added or removed from the queue to facilitate processing of the items. Some queues are intended to be used by a single processing thread (thread), while others may be accessed concurrently by more than one different thread.
For example, within the Java™ programming language, a package called java.util.concurrent provides a variety of classes including one referred to as “ConcurrentLinkedQueue”. A ConcurrentLinkedQueue, or more generally, a concurrent linked queue, is an unbounded thread-safe queue based on linked nodes. A ConcurrentLinkedQueue is used when many threads will share access to a common collection of items. The class does not permit the use of null elements. The ConcurrentLinkedQueue class provides a set of complex algorithms for managing an instance of a concurrent linked queue in the Java™ programming language.
The ConcurrentLinkedQueue class utilizes volatile variables and atomic operations, in software, to effectuate concurrent queue management. Accesses to variables denoted as “volatile,” at least in the Java™ programming language, are typically slower than accesses to regular, or non-volatile, variables. “Atomicity” of an operation refers to a property in which the operation is executed completely or not at all. An atomic operation includes a plurality of instructions. To other processing threads, the operation executes uninterrupted as if a single instruction. Atomic actions cannot be interleaved, so atomic actions can be used without interference from other threads.
The use of volatile variables and atomic operations in managing a concurrent linked queue results in slower execution. This is particularly true when compared to a non-concurrent linked queue implementation.